The invention relates to a method for in a relatively slow background memory searching a desired record in an ordered list of records through an iterative search along a particular search path comprising a number of branches, the actual search path being chosen from a plurality of predetermined and partially joint search paths, wherein each record has a unique identifying key and a given search-value identifies the desired record, the method comprising after selecting the first branch of the particular search path as the actual branch the steps of:
a) copying the key of a record at the terminating node of the actual branch into a relatively fast foreground memory and making a comparison between said key and the search-value; PA1 b) selecting, under control of the comparison, one of the branches starting at said node as a new actual branch, or selecting the record having said key as the desired record; PA1 c) repeating steps a) and b) for the new actual branch, until the comparison yields correspondence or until the actual branch corresponds to a single record without the desired record having been found. PA1 a) read means for copying the key of a record at the terminating node of the actual branch into a relatively fast foreground memory and making a comparison between said key and the search-value; PA1 b) selection means for selecting, under control of the comparison, one of the branches starting at said node as a new actual branch, or selecting the record having said key as the desired record; PA1 c) repeat means for repeated activation of the read means and the selection means for the new actual branch, until the comparison yields correspondence or until the actual branch corresponds to a single record without the desired record having been found. PA1 a) copying the key of a record halfway the actual list into a relatively fast foreground memory and making a comparison between said key and the search-value; PA1 b) selecting, under control of the comparison, either the first or the second half of the actual list as a new list, or selecting the record having said key as the desired record; PA1 c) repeating steps a) and b) for the new list, until the comparison yields correspondence or until the actual list has a single record without the desired record having been found.
The invention further relates to an apparatus for in a relatively slow background memory searching a desired record in an ordered list of records through an iterative search along a particular search path comprising a number of branches, the actual search path being chosen from a plurality of predetermined and partially joint search paths, wherein each record has a unique identifying key and a given search-value identifies the desired record, the apparatus comprising:
The invention further relates to a TMC receiver for the reception of traffic messages, comprising a receiving unit for the reception of a search-value and a reading unit for reading data from a background memory.
An example of the above-mentioned iterative search is the so-called binary search. Binary search is a well known method for searching a desired record in an ordered list of records and is described for example on page 14 of the text book "Algorithms+data structures=programs" by Niklaus Wirth, Prentice-Hall, 1976, ISBN 0-13-022418-9. In the binary search technique, the key of the record halfway through the ordered list is compared with a given search value. If the key is not equal to the search-value then the result of the comparison determines whether the desired record is to be found in the first half of the list or in the second half of the list. Subsequently, the key of the record halfway the respective half of the list is compared with the search-value. These steps of comparing the key and of dividing the list into two parts are repeated until the desired record is found or until it is determined that the desired record is absent.
It is known to apply the binary search technique to the searching of a list of records which resides in a relatively slow background memory. In such a case, the step of comparing the key of a record in the list includes copying at least the key of that record from the background memory into the relatively fast foreground memory in which the program executing the binary search is running. The known method has a problem in that it takes a relatively long time to copy the key from the background memory into the foreground memory. This significantly slows down the program executing the binary search since usually various comparison steps are required and, therefore, various keys have to be copied from the background memory into the foreground memory.